import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-17
 * Time: 上午 10:44
 */
public class Test {
    /**
     * 数组中的逆序对数
     */
    //1.暴力解法：
    public static void main1(String[] args) {
        Scanner input = new Scanner(System.in);
        String[] cur = input.nextLine().split(" ");
        int count = 0;
        int[] arr = new int[cur.length];
        for (int i = 0; i < cur.length; i++) {
            arr[i] = Integer.parseInt(cur[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i - 1; j >=0; j--) {
                if (arr[j] > arr[i]) count++;
            }
        }
        System.out.println(count);
    }
    //2.归并排序解法
    public static int reversePairs (int[] arr) {
        int len = arr.length;
        if (len < 2) return 0;
        return reversePairs(arr, 0, len - 1);
    }

    public static int reversePairs(int[] arr,int left, int right){
        if (left == right) return 0;
        int mid = (left + right) / 2;
        int leftPairs = reversePairs(arr,left,mid);
        int rightPairs = reversePairs(arr,mid + 1, right);
        int mergeCount = mergeAndCount(arr, left, mid, right);
        return leftPairs + rightPairs + mergeCount;
    }
    public static int mergeAndCount(int[] arr,int left, int mid, int right){
        int count = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        int[] arr1 = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) arr1[k++] = arr[s1++];
            else {
                arr1[k++] = arr[s2++];
                count  = (count + mid - s1 + 1) % 1000000007;
            }
        }
        while (s1 <= e1) arr1[k++] = arr[s1++];
        while (s2 <= e2) arr1[k++] = arr[s2++];
        for (int i = 0; i < k; i++) arr[i + left] = arr1[i];
        return count;
    }

    public static void main(String[] args) {
        int[] arr = { 364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575 };
        System.out.println(reversePairs(arr));
    }
}
